#include "./huffman-tree-static.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void selectMin(HTNode *nodes, int count, int *n1, int *n2)
{
	int i;
	// 先选择第一个没有双亲节点的节点
	for (i = 0; i < count; i++)
	{
		if (nodes[i].parent == -1)
		{
			*n1 = i;
			break;
		}
	}
	// 然后选择出没有双亲节点且权值最小的节点
	for (i = *n1 + 1; i < count; i++)
	{
		if (nodes[i].parent == -1 && nodes[i].weight < nodes[*n1].weight)
		{
			*n1 = i;
		}
	}
	// 然后选出第二个没有双亲节点且权值不等于第一个节点的节点
	for (i = 0; i < count; i++)
	{
		if (nodes[i].parent == -1 && nodes[i].weight != nodes[*n1].weight)
		{
			*n2 = i;
			break;
		}
	}
	// 最后选择出第二个没有双亲节点且权值最小且不等于n1的节点（权值大于n1节点）
	for (i = *n2 + 1; i < count; i++)
	{
		if (nodes[i].parent == -1 && i != *n1 && nodes[i].weight < nodes[*n2].weight)
		{
			*n2 = i;
		}
	}
}

HuffmanTree *createHuffmanTree(char nodes[], int weight[], int count)
{
	// 总节点数，遍历下标
	int total = 2 * count - 1, i;
	// 初始化全部节点
	HTNode *treeNodes = (HTNode *)calloc(total, sizeof(HTNode));
	// 先给叶子节点赋值
	for (i = 0; i < count; i++)
	{
		treeNodes[i].data = nodes[i];
		treeNodes[i].weight = weight[i];
		treeNodes[i].parent = treeNodes[i].left = treeNodes[i].right = -1;
	}
	// 开始进行构建
	// 霍夫曼树节点数组的前面n个是叶子节点，因此合并时新节点放到后面下标n到2n - 2处
	// 最小的两个节点下标
	int n1, n2;
	for (i = count; i < total; i++)
	{
		// 选择（每选择并组装一次，有效节点多一个，恰好等于i的值）
		selectMin(treeNodes, i, &n1, &n2);
		// 组装
		treeNodes[i].data = 0;
		treeNodes[i].weight = treeNodes[n1].weight + treeNodes[n2].weight;
		treeNodes[i].parent = -1;
		treeNodes[i].left = n1;
		treeNodes[i].right = n2;
		treeNodes[n1].parent = treeNodes[n2].parent = i;
	}
	// 创建霍夫曼树对象并返回
	HuffmanTree *tree = (HuffmanTree *)malloc(sizeof(HuffmanTree));
	tree->nodes = treeNodes;
	tree->leafCount = count;
	// 找到根节点（还剩下的那个没有双亲节点的节点）
	for (i = 0; i < total; i++)
	{
		if (treeNodes[i].parent == -1)
		{
			tree->root = i;
			break;
		}
	}
	return tree;
}

int getWPL(HuffmanTree *tree)
{
	// 从每个叶子节点开始往上进行统计
	// 表示遍历下标、当前节点权值以及带权路径值
	int i, weight, WPL = 0;
	// 遍历时节点指针
	HTNode *pointer;
	for (i = 0; i < tree->leafCount; i++)
	{
		// 先记录当前权值
		weight = tree->nodes[i].weight;
		// 从当前节点向上查找直到根节点为止
		for (pointer = &tree->nodes[i]; pointer->parent != -1; pointer = &tree->nodes[pointer->parent])
		{
			WPL += weight;
		}
	}
	return WPL;
}

/**
 * 反转字符串
 * @param str 传入的字符串
 */
void strReverse(char *str)
{
	int length = strlen(str);
	// 分别指向头尾
	int i = 0, j = length - 1;
	char temp;
	while (i < j)
	{
		temp = str[i];
		str[i] = str[j];
		str[j] = temp;
		i++;
		j--;
	}
}

CodeMap *huffmanCoding(HuffmanTree *tree)
{
	CodeMap *map = (CodeMap *)malloc(sizeof(CodeMap));
	map->count = tree->leafCount;
	map->codeResults = (Code *)calloc(map->count, sizeof(Code));
	// 从每个叶节点开始往上索引编码
	// 分别表示遍历下标、字符串编码时的字符串下标和每次向上索引时，记录当前节点的下标
	int i, strIndex, currentIndex;
	// 向上索引时的指针
	HTNode *pointer;
	for (i = 0; i < tree->leafCount; i++)
	{
		map->codeResults[i].data = tree->nodes[i].data;
		char code[100];
		currentIndex = i;
		strIndex = 0;
		for (pointer = &tree->nodes[i]; pointer->parent != -1; pointer = &tree->nodes[pointer->parent])
		{
			if (currentIndex == tree->nodes[pointer->parent].left)
			{
				code[strIndex] = '0';
			}
			else
			{
				code[strIndex] = '1';
			}
			strIndex++;
			// 记录当前节点的双亲节点下标，即为下一次的当前下标
			currentIndex = pointer->parent;
		}
		// 结束字符串
		code[strIndex] = 0;
		// 反转字符串
		strReverse(code);
		// 设定编码对象
		map->codeResults[i].code = (char *)calloc(strlen(code) + 1, sizeof(char));
		strcpy(map->codeResults[i].code, code);
	}
	return map;
}

void preorderTraverse(HuffmanTree *tree, int nodeIndex)
{
	if (nodeIndex != -1)
	{
		char data = tree->nodes[nodeIndex].data == 0 ? '^' : tree->nodes[nodeIndex].data;
		printf("%c:%d ", data, tree->nodes[nodeIndex].weight);
		preorderTraverse(tree, tree->nodes[nodeIndex].left);
		preorderTraverse(tree, tree->nodes[nodeIndex].right);
	}
}

void inorderTraverse(HuffmanTree *tree, int nodeIndex)
{
	if (nodeIndex != -1)
	{
		char data = tree->nodes[nodeIndex].data == 0 ? '^' : tree->nodes[nodeIndex].data;
		inorderTraverse(tree, tree->nodes[nodeIndex].left);
		printf("%c:%d ", data, tree->nodes[nodeIndex].weight);
		inorderTraverse(tree, tree->nodes[nodeIndex].right);
	}
}

void postorderTraverse(HuffmanTree *tree, int nodeIndex)
{
	if (nodeIndex != -1)
	{
		char data = tree->nodes[nodeIndex].data == 0 ? '^' : tree->nodes[nodeIndex].data;
		postorderTraverse(tree, tree->nodes[nodeIndex].left);
		postorderTraverse(tree, tree->nodes[nodeIndex].right);
		printf("%c:%d ", data, tree->nodes[nodeIndex].weight);
	}
}